#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    TreeNode* _build(vector<int>& preorder, vector<int>& inorder, int& i, int begini, int endi)
    {
        if (begini > endi)
        {
            return nullptr;
        }

        TreeNode* root = new TreeNode(preorder[i]);

        int j = 0;
        while (preorder[i] != inorder[j])
        {
            j++;
        }
        i++;
        // [0,begin-1] root[begin+1,endi]
        root->left = _build(preorder, inorder, i, 0, j - 1);
        root->right = _build(preorder, inorder, i, j + 1, endi);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int prei = 0, begini = 0, endi = sizeof(preorder.size() - 1);
        return  _build(preorder, inorder, prei, begini, endi);
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

template<size_t N>
void test(int a = N)
{
    return 0;
}

int main()
{
    int a[] = { 3,9,20,15,7 };
    vector<int> p(a, a + sizeof(a));

    int b[] = { 9,3,15,20,7 };
    vector<int> q(b, b + sizeof(b));
    return 0;
}